package com.huawei.su;

import java.util.Stack;

/**
 * 删除链表的倒数第n个节点
 * https://www.nowcoder.com/practice/f95dcdafbde44b22a6d741baf71653f6?tpId=295&tqId=727&ru=%2Fpractice%2F886370fe658f41b498d40fb34ae76ff9&qru=%2Fta%2Fformat-top101%2Fquestion-ranking&sourceUrl=%2Fexam%2Foj
 */
public class BM9 {
    public static void main(String[] args) {
        ListNode listNode1 = new ListNode(1);
        ListNode listNode2 = new ListNode(2);
        ListNode listNode3 = new ListNode(3);
        ListNode listNode4 = new ListNode(4);
        ListNode listNode5 = new ListNode(5);
        listNode1.next = listNode2;
        listNode2.next = listNode3;
        listNode3.next = listNode4;
        listNode4.next = listNode5;

        removeNthFromEnd(listNode1,2);
    }

    public static ListNode removeNthFromEnd (ListNode head, int n) {
        if(head==null || (head.next ==null && n == 1)){
            return null;
        }

        ListNode index0 = head;
        Stack<ListNode> stack0 = new Stack<>();
        while(true){
            if(index0==null){
                break;
            }
            stack0.push(index0);
            index0 = index0.next;
        }
        int count = 0;

        Stack<ListNode> stack1 = new Stack<>();
        while (true){
            if(stack0.isEmpty()){
                break;
            }
            count++;
            if(count == n){
                stack0.pop();
                continue;
            }
            stack1.push(stack0.pop());
        }

        ListNode newHead = stack1.pop();
        ListNode index1  = newHead;
        while (true){
            if(stack1.isEmpty()){
                index1.next = null;
                break;
            }
            index1.next = stack1.pop();
            index1 = index1.next;
        }
        return newHead;
    }
}
